1. Field of the Invention
The present invention generally relates to a Low Density Parity Check (LDPC) code, and more particularly to a method for puncturing an LDPC code.
2. Description of the Related Art
Because Low Density Parity Check (LDPC) codes have a superior performance and lower decoding complexity than turbo codes and can be processed in parallel at a high rate, they are attracting much interest as a coding scheme suitable for next generation communication systems.
The LDPC codes first proposed by Gallager in 1962 are defined as linear block codes using a parity check matrix H with a large number of 0's. The technology required to process the codes has not been actively implemented due to code complexity, and therefore the LDPC codes have been almost forgotten for a long time. Mackay and Neal have rediscovered the LDPC codes and have verified that they have a superior performance using a simple probabilistic decoding method.
The LDPC code is defined by a sparse random parity check matrix H with a small number of 1's. The parity check matrix H is used to determine whether a received codeword has been decoded normally. If a product of the decoded codeword and the parity check matrix H is 0, it is determined that no error has occurred. After the predetermined parity check matrix of an LDPC code is designed to produce zero when it is multiplied by any codeword, an encoding operation in an encoder of a transmitter is performed on the basis of the designed parity check matrix.
The parity check matrix H has the following structural characteristics. First, a weight k per row is uniformly constructed. Second, a weight j per column is constructed by the given distribution. Third, overlap between any two columns is made at random and is not greater than 1. Herein, the weight indicates the number of non-zero elements, i.e., the number of 1's. The overlap between two columns is their inner product. The weight of a row or column is much less than a code length. For this reason, the code are called as low density parity check codes.
Techniques capable of generating LDPC codes at various code rates are divided into two methods. The first method is designed such that parity check matrices with various code rates can be included in one main parity check matrix. This method generates the parity check matrices based on the various code rates suitable for constraints while generating the main parity check matrix. The LDPC codes generated from the above-described method can have superior performance, and a performance at each code rate can be predicted. However, this method can obtain only limited number of code rates and cannot be applied to full or partial Incremental Redundancy (IR) of an Hybrid Automatic Repeat Request (H-ARQ) system requiring the technology of combining code bits due to a mismatch between coded bit streams at various code rates.
The second method performs a puncturing process suitable for varying the code rate after an encoding process. After a transmitter performs the puncturing process in a puncturing pattern, a decoder of a receiver inserts a Log Likelihood ratio (LLR) value of 0 or a probability value of 0.5 into a punctured bit node. The puncturing process can easily generate a desired code rate and does not increase complexity in the encoding process. Moreover, the puncturing process can be applied to the H-ARQ technology as in a Rate Compatible Punctured Turbo (RCPT) scheme. However, a performance of the second method is inferior to that of the first method based on LDPC codes with an optimal parity check matrix at each code rate.
To overcome this drawback, a method for designating a puncturing distribution in an optimal parity check matrix with respect to existing irregular codes has been proposed. This method can designate puncturing ratios according to the degree distribution of bit nodes by using the density evolution technique. However, because this method is based on an asymptotic behavior under the assumption that a block length, a cycle length, and the number of iterative decoding processes are ideal, it is not useful for an actual system with a finite block length. Moreover, because a puncturing position is designated according to the degree distribution, the above-described method cannot be applied to regular codes. It is difficult to give a priority among bit nodes with the same node degree also in the irregular codes.
Another puncturing technique has been proposed which performs a puncturing process for LDPC codes with a finite length by grouping the same-step recoverable nodes. The group-wise puncturing process cannot be applied in a precise bit-wise puncturing. However, this puncturing technique only takes into consideration that an LLR of punctured bits is quickly filled from the point of view of a bit node, without taking into consideration information received from many check nodes.
On the other hand, another block-wise puncturing technique has been proposed which is suitable for an LDPC code with a dual diagonal parity structure. This puncturing technique can be applied to only the block LDPC code with a dual diagonal parity structure and performs the puncturing process without taking into consideration the degree of a bit node, such that the maximum number of punctured bit nodes connected to each check node cannot be not minimized.